HNSW with Accuracy Guarantees Using Graph Spanners -- A Technical Report
基于图Spanner的HNSW精度保证框架
🧭 近似最近邻检索 · 精度保证
University of Toronto · The University of Texas at Arlington · IIT Bombay
通过Certify-then-Rectify框架，动态认证HNSW搜索并利用spanner理论提供最坏情况正确性保证
📌 工作参考价值（4 点）
- 可在线部署轻量级认证器评估HNSW召回质量，避免因贪婪搜索遗漏关键近邻，适合高召回率场景（如广告匹配）。
- 利用极值理论估计spanner拉伸因子提供距离上界，无需重建索引即可动态平衡效率与准确性。
- 过滤搜索扩展可直接应用于带属性约束的商品向量检索（如分类、价格筛选），提升复杂查询的可靠性。
- 分层纠正策略允许在绝大多数查询中保持HNSW速度，仅在必要时触发精确搜索，适合大规模在线服务。